package com.salim.leetcode.$79;

import java.util.Arrays;

public class WordSearch {
    //最初的思路是深拷贝数组 还发现二维数组不能用arrays.clone 或System.copy做深拷贝
    //改进版可以不用copy 递归完还原即可
    public boolean exist(char[][] board, String word) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0)){
                    if(word.length()==1){
                        return true;
                    }
                    if(loop(board,0,i,j,word)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean loop(char[][] board, int beginIndex, int nextI, int nextJ, String word){
        if(nextI>=board.length||
            nextJ>=board[0].length||
            nextI<0||
            nextJ<0||
            board[nextI][nextJ]>127||
            beginIndex>=word.length()){
            return false;
        }
        if(board[nextI][nextJ]==word.charAt(beginIndex)){
            if(beginIndex==word.length()-1){
                return true;
            }
            board[nextI][nextJ]+=128;
            if(loop(board,beginIndex+1,nextI-1,nextJ,word)||
                loop(board,beginIndex+1,nextI+1,nextJ,word)||
                loop(board,beginIndex+1,nextI,nextJ-1,word)||
                loop(board,beginIndex+1,nextI,nextJ+1,word)){
                return true;
            }
            board[nextI][nextJ]-=128;
            return false;
        }else{
            return false;
        }
    }
}
